package algorithm.easy;

import java.util.Stack;

public class Solution155 {

    //设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
    // 实现 MinStack 类:
    // MinStack() 初始化堆栈对象。
    // void push(int val) 将元素val推入堆栈。
    // void pop() 删除堆栈顶部的元素。
    // int top() 获取堆栈顶部的元素。
    // int getMin() 获取堆栈中的最小元素。

    //["MinStack","push","push","push","getMin","pop","top","getMin"]
    //[[],[-2],[0],[-3],[],[],[],[]]
    //
    //输出：
    //[null,null,null,null,-3,null,0,-2]
    //
    //解释：
    //MinStack minStack = new MinStack();
    //minStack.push(-2);
    //minStack.push(0);
    //minStack.push(-3);
    //minStack.getMin();   --> 返回 -3.
    //minStack.pop();
    //minStack.top();      --> 返回 0.
    //minStack.getMin();   --> 返回 -2.
    static class MinStack {
        Integer min = Integer.MAX_VALUE;
        Stack<Integer> stack ;
        public MinStack() {
            stack = new Stack<>();
        }

        public void push(int val) {
            if(min >=val){//获取第二小值，压栈(记忆上一次最小的),即-记住上一次最小的那个记录
                stack.push(min);
                min = val; //当前最小标记位
            }
            stack.push(val);
        }

        public void pop() {
            Integer val = stack.pop();
            if(val==min){// 表示当前最小
                min = stack.pop();
            }
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return min;
        }
    }
    static class MinStack2 {
        Integer min = null;
        Stack<Integer> stack1 ;
        Stack<Integer> stack2 ;
        public MinStack2() {
            stack1 = new Stack<>();
            stack2 = new Stack<>();
        }

        public void push(int val) {
            if(min==null){
                min = val;
            }
            if(min >=val){//获取第二小值，压栈
                min = val;
            }
            stack2.push(min);
            stack1.push(val);
        }

        public void pop() {
            stack1.pop();
            stack2.pop();

        }

        public int top() {
            return stack1.peek();
        }

        public int getMin() {
            return stack2.peek();
        }
    }


    public static void main(String[] args){
        MinStack2 minStack = new MinStack2();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());  // --> 返回 -3.
        minStack.pop();
        System.out.println( minStack.top());     // --> 返回 0.
        System.out.println(minStack.getMin());  // --> 返回 -2.
    }
}
